﻿#pragma once
#include<iostream>
#include<vector>
using namespace std;

//除留余数法：
//是构建哈希表的一种方式，大致思路为通过对存储的数据取余（数据可存储空间的长度），
//将处理后得到的余数作为下标映射到存储空间中，即“假设哈希表的大小为M，
//那么通过key除以M的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M”
//但是，使用此方法需尽可能避免存储空间大小为2的幂或10的幂，会造成严重的哈希冲突（哈希冲突即多个数对应到了一个地址）
//在此方法中，用于存储空间(以下实现中，指的是vector的size，而非capacity）大小的最佳实践为不太接近2的整数次幂的质数
//（尽管如此，哈希冲突是不可避免的，选取合适的哈希函数作用只是尽可能减少哈希冲突，因此就需要能够合理处理哈希冲突的方案了）
//同时，此方法的负载因子最好控制在0.7以下，当负载因子超过该值，需进行扩容操作
//（负载因子即为实际存入的数据除以用于存入数据的空间得到的数值，当负载因子较大时，空间利用率高，减少资源浪费，但此时哈希冲突概率高，而负载因子较小时情况相反）
// 
// 
//开放定址法：
//是解决哈希冲突的一种思路，即若出现了哈希冲突，则将此数据通过某种规律存放入其他地址
//此思路衍生出了三种具体方式：
//1.线性探测（效率相对较低）：
//  但出现哈希冲突时，以此位置（hash0）为起点，以线性方式（hash0 + i）向后查询，直至Empty位，对该数据进行存储
//	注：在存储空间未满的情况下若达到了存储地址的尾，便需要通过类似顺序队列的方式进行取余运算至存储空间头部
//2.二次探测（跳跃探测，冲突率低于线性探测，但可能死循环）：
//  与线性探测思路类似，也是以哈希冲突位置为起点，使用某种规律进行Empty位的探测，但二次探测的规律为，
//	hash0 +/- i*i（每次+-一轮后，++i）
//  注：此方式可以不使用取余法找前半部分的存储空间，但该方法查找效率虽优于线性探测，
//		但在某些特定情况会出现因子不大于0.7（即有空位置）但查找不到（陷入死循环）的情况，因此，该方法并非最优解
//3.双重散列（为开放定址法中最优解，本身是跳跃探测，但冲突率低于二次探测，且可通过合理的公式避免死循环）：
//  第一个哈希函数计算出的值发生冲突时，使用第二个哈希函数计算出一个跟key相关的偏移量值，不断往后探测，直到寻找到下一个没有存储数据的位置为止
//两个哈希函数分别为：
//1. h1(key) = hash0 = key  % M
//2. hc(key, i) = hashi = (hash0 + i ∗ h2(key)) % M， i  = { 1, 2, 3, ..., M }



//关于除留余数法扩容方案：
//C++底层使用了质数表（包含了适合作为扩容值的质数）来指定扩容值，
//当需要扩容时，使用当前容量在质数表的下一个值进行扩容即可，
//注：虽然质数表中的数据是有限的，但目前无需担心数据量会大到超过质数表最大值
//	  因为最大值为42亿+，若使用开放定址法，每个位置仅存放一个char都会占据4G内存，若为结构体显然会极大，
//	  且由于一般哈希会采用链链地址法，其中每个位置至少需要一个指针变量（8字节），若需要启用质数表最大值，
//    则所占据的内存是相当恐怖的


//关于key为不能直接使用除留余数法（无法取余）的类型时：
//key的类型可能为string，double，值也可以是负数，面对类似情况，无法直接取余，
//那么，就需要为HashTable类模板传递‘可以将string等无法直接取余的类型值顺利转换为可求余’的仿函数
//（即HashTable的第三个模板参数）


//关于自定义类型作为key时：
//由于需要判断key值是否冗余等原因，该自定义类型需包含==运算符重载，
//但由于库中某些类不含有==运算符重载，所以HashTable诞生了第四个模板参数


//下面以实现不允许键值冗余的除留余数法+线性探测构建的k_v型Hash为例

//在诸如find接口中，需要在EMPTY时停止，DELETE时继续，因此创建相关枚举
enum State
{
	EXIST,//存在
	EMPTY,//空
	DELETE//删除
};
//每个空间都需要存放当前空间的情况与pair<K, V>，因此，需创建HashData类模板
template<class K, class V>
struct HashData
{
	//这里使用了struct构建了类，因此可以暂且不写构造函数，可以在外部为_kv赋值
	pair<K, V> _kv = pair<K, V>();
	State _state = EMPTY;//一个位置的初始状态一定为EMPTY
};
//转换key为可求余值的仿函数
template<class K>
struct HashFunc
{
	//此方案可用于处理小数与负数且能兼容处理正整数（仅为示例，具体需构建能尽可能减少哈希冲突的方案）：
	unsigned long operator()(K key)
	{
		return (unsigned long)key;//直接将key显示类型转换为unsigned long类型
	}
};
//使用类模板特化，设计针对K为string的仿函数
//字符串转换成整形，最简单的办法就是把字符ascii码值相加
//但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的 
//这里我们使用BKDR哈希（真正能够解决K为stirng的方法）的思路，
//用上次的计算结果去乘以一个质数，且这个质数一般取31, 131等效果会比较好
template<>
struct HashFunc<string>
{
	unsigned long operator()(string key)
	{
		unsigned long hash = 0;
		for (const auto& e : key)
		{
			hash += e;
			hash *= 131;//注：BKDR哈希的方案面对长字符串很可能会溢出，但这也无所谓，
			//因为目的是将字符串转换为一个可求余的数，所以就算溢出也问题不大
		}
		return hash;
	}
};
//==运算符重载仿函数（这里只是举个例子，就先不做自定义类型的具体实现了）
template<class K>
struct Compare
{
	Compare(const K& key)
		:_key(key)
	{
	}
	bool operator==(K other)
	{
		return _key == other;
	}
	K _key;
};
//提供扩容数值的函数
inline unsigned long __stl_next_prime(unsigned long n)//注：inline为内联函数关键字，这里的函数参数为size
{
	//质数表
	static const int __stl_num_primes = 28;//表示质数表中数据个数为28个
	static const unsigned long __stl_prime_list[__stl_num_primes] =
	{
	53, 97, 193, 389, 769,
	1543, 3079, 6151, 12289, 24593,
	49157, 98317, 196613, 393241, 786433,
	1572869, 3145739, 6291469, 12582917, 25165843,
	50331653, 100663319, 201326611, 402653189, 805306457,
	1610612741, 3221225473, 4294967291
	};
	const unsigned long* first = __stl_prime_list;
	const unsigned long* last = __stl_prime_list +
		__stl_num_primes;
	//lower_bound函数返回第一个参数到第二个参数的左闭右开区间中第一个大于等于n的值
	const unsigned long* pos = lower_bound(first, last, n);
	return pos == last ? *(last - 1) : *pos;//当n已经为质数表最大值时，仍返回该值，确保哈希表至少有一个可用的容量值（此时不代表空间存满，只是因子较大，冲突会加剧，因此仍可继续使用该值）
}

namespace open_address//命名空间——开放定址法
{
	//创建HashTable类模板
	template<class K, class V, class HashFunc = HashFunc<K>, class Compare = Compare<K>>
	class HashTable
	{
		typedef HashData<K, V> HashData;
		HashFunc hashfunc;//转换key值的仿函数对象（也可在需要是创建临时对象来进行函数调用，
						  //这里采用了直接实例化仿函数对象作为私有成员变量便于使用）
	public:
		HashTable()
			//:_tables(11)
			//:_tables(4)
			:_tables(__stl_next_prime(0))//使用质数表第一个值
		{
		}

		bool Insert(const pair<K, V>& kv)
		{
			//通过find进行判断，当键值冗余时，直接返回false
			if (Find(kv.first).first == true)
			{
				return false;
			}
			//当负载因子大于0.7时，需要扩容
			//注：这里最直观的写法是创建临时成员tables，将其在_tables.size()的基础上进行质数扩容，
			//	  随后将当前_tables的元素通过哈希函数全部重新插入到tables中（不能直接使用范围for将_tables的元素拷贝到tables中，这样会打破哈希函数）
			//    最终与_tables进行swap（注：swap仅交换指针及成员变量，无需进行深拷贝，效率高于赋值运算符重载，因此此处采用swap）
			//	  但这样会重复使用insert中的插入代码，致使代码冗余，
			//	  事实上，这里可以采取现代写法创建ht临时成员，直接实现Insert的代码复用
			if (_size * 1.0 / _tables.size() > 0.7)//可以采用将其中一个操作数*1.0的方式来避免/运算符面对整形的自动向下取整
			{
				HashTable ht;
				//ht._tables.resize(_tables.size() * 2);//这里参数最优解应为一个质数，这里暂且*2，后续会进行调整
				ht._tables.resize(__stl_next_prime(_tables.size() + 1));//使用质数表中质数进行扩容
				for (const auto& e : _tables)
				{
					if (e._state == EXIST)
					{
						ht.Insert(e._kv);//由于此时ht._tables的容量比_tables的容量大，所以无需担心此处insert会再次进行扩容操作
					}
				}
				swap(ht._tables, _tables);//这里采取效率更高的swap，直接交换容器的成员变量，而非使用赋值运算符重载进行深拷贝，提高了效率
			}
			size_t hash0 = hashfunc(kv.first) % _tables.size();//取余定位存储位置
			//当定位的位置存在元素时，进行线性探测
			if (_tables[hash0]._state == EXIST)
			{
				size_t i = 1;
				size_t hash1 = (hash0 + i) % _tables.size();
				while (_tables[hash1]._state == EXIST)//由于负载因子需在0.7以内，因此无需担心死循环，一定可以找到空位置
				{
					++i;
					hash1 = (hash0 + i) % _tables.size();
				}
				_tables[hash1]._kv = kv;
				_tables[hash1]._state = EXIST;
			}
			//当定位到的位置不存在元素时，直接将kv存储即可
			else {
				_tables[hash0]._kv = kv;
				_tables[hash0]._state = EXIST;
			}
			++_size;
			return true;
		}
		//Find查找思路：先使用哈希函数锁定位置，若此位置非所求，
		//则进行线性探测，当该位置状态为EXIST时，再次进行判断；
		//若为DELETE，则继续探测；若为EMPTY，则停止搜索，返回false
		pair<bool, V&> Find(const K& key)
		{
			size_t hash0 = hashfunc(key) % _tables.size();
			//若直接通过哈希函数查找到
			if (Compare(_tables[hash0]._kv.first) == key)
			{
				return pair<bool, V&>(true, _tables[hash0]._kv.second);
			}
			//若未直接找到，则进行线性探测
			size_t i = 1;
			size_t hash1 = (hash0 + i) % _tables.size();
			//当状态非空时，继续线性探测
			while (_tables[hash1]._state != EMPTY)//由于负载因子需不大于0.7，所以一定可以走到空（但需注意，初始值不能给1）
			{
				if (_tables[hash1]._state == EXIST && _tables[hash1]._kv.first == key)//当状态为存在且与key相等
				{
					return pair<bool, V&>(true, _tables[hash1]._kv.second);
				}
				++i;
				hash1 = (hash0 + i) % _tables.size();
			}
			//退出循环时即为找到EMPTY时，返回false
			return pair<bool, V&>(false, _tables[hash0]._kv.second);//最好不要返回kv.second，这里有待改善->最终敲定返回指针（链地址法），不过这里就暂且不改了
		}
		//Erase实现思路：使用哈希函数+线性探测，若找到，则将其状态置为DELETE即可
		//循环条件同样为状态非EMPTY
		bool Erase(const K& key)
		{
			size_t hash0 = hashfunc(key) % _tables.size();
			//若直接通过哈希函数查找到
			if (Compare(_tables[hash0]._kv.first) == key)
			{
				_tables[hash0]._state = DELETE;
				--_size;
				return true;
			}
			//若未直接找到，则进行线性探测
			size_t i = 1;
			size_t hash1 = (hash0 + i) % _tables.size();
			//当状态非空时，继续线性探测
			while (_tables[hash1]._state != EMPTY)
			{
				if (_tables[hash1]._state == EXIST && Compare(_tables[hash1]._kv.first).operator==(key))
				{
					_tables[hash1]._state = DELETE;
					--_size;
					return true;
				}
				++i;
				hash1 = (hash0 + i) % _tables.size();
			}
			//退出循环时即为找到EMPTY时，返回false
			return false;
		}
		size_t Size()
		{
			return _size;
		}
		void Print()
		{
			for (const auto& e : _tables)
			{
				if (e._state == EXIST)
				{
					cout << "key: " << e._kv.first << " val: " << e._kv.second << endl;
				}
			}
		}
	private:
		vector<HashData> _tables;//使用vector实现哈希表整体（姑且先将允许存放数据的空间设置为11）
		size_t _size = 0;//_size记录真实的已存储数据，用于计算负载因子，以便进行扩容操作
	};
}

//出现的错误：
//1.在扩容时使用了范围for遍历源_tables，但忘记判断e._state，导致空值也被插入，造成错误
//2.使用开放定址法+负载因子不大于0.7的前提是起始存储空间不为1，2，3，否则会造成存储空间满的情况，导致Find接口陷入死循环
//3.意外将扩容作为if，插入新元素作为对应的else，导致每次扩容都不会插入新元素，发现后去除了插入新元素的else
//4.lower函数的功能为找到区间中第一个不小于参数的值，所以扩容时需要使用__stl_next_prime(_tables.size() + 1)而非__stl_next_prime(_tables.size())
//5.Erase接口忘记维护size了，差点没发现